💰 Fractional Knapsack Problem

Maximize value using the Greedy (Ratio) approach.

🎒 Knapsack Problem Statement

We are given $n$ objects, each with a weight $c[i]$ and a value $v[i]$. Our goal is to fill a knapsack with maximum capacity $W$ to maximize the total value. Since this is the **Fractional** Knapsack problem, we can take fractions of objects.

Current Item Data:

Object No. Weight (Kg) Value (Rs.) Value/Weight Ratio (Rs./Kg)

🧠 The Greedy Strategy (Ratio-Based)

The Key Metric: Value-to-Weight Ratio

The greedy choice is to always pick the item that gives the most value for the least weight. This is achieved by sorting the objects based on their **Value-to-Weight Ratio ($\frac{v}{c}$)** in **descending** order.

  1. **Calculate Ratios:** For every object $i$, calculate $\text{Ratio}_i = \frac{v[i]}{c[i]}$.
  2. **Sort:** Arrange all objects based on $\text{Ratio}_i$ from highest to lowest.
  3. **Fill:** Iterate through the sorted list:
    • If the **entire object** fits, take it and update the remaining capacity.
    • If only a **fraction** fits, take the fraction needed to fill the knapsack completely, and stop.

Ratios for Sample Input (Sorted):

Object No. Weight (Kg) Value (Rs.) Value/Weight Ratio (Rs./Kg)

🎬 Step-by-Step Execution

Capacity (W): 50Kg | Total Value: Rs. 0.00 | Step: 0

Item Processing Order:

Step Index Object No. Ratio Status

Knapsack Log: (Required Output Format)

Prepare the data and click Start Demo to begin.

📊 Analysis & Complexity

Time Complexity

O(n log n)

Dominated by the **sorting** step (e.g., using Merge Sort or Quick Sort). The subsequent filling loop takes only $O(n)$ time.

Space Complexity

O(n)

Required to store the item objects, their values, weights, and the calculated ratios.

Why Greedy Works Here

The Greedy approach works perfectly for the **Fractional** Knapsack Problem because we can take partial amounts. Once we commit to the highest value-to-weight ratio, there is no way to achieve a better overall value, even if we were to look ahead. This is unlike the 0/1 Knapsack Problem, where a greedy choice might prevent a better overall solution later.